package com.duoduo.滑动窗口;

import java.util.Arrays;

/**
 * @program: algorithm 567
 * @description: 字符串的排列  可以参考242题
 * 给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
 * <p>
 * 换句话说，s1 的排列之一是 s2 的 子串 。
 * 输入：s1 = "ab" s2 = "eidbaooo"
 * 输出：true
 * 解释：s2 包含 s1 的排列之一 ("ba").
 * @author: chaidl  ！
 * @create: 2022-03-18 16:15
 */
public class 字符串的排列 {
    public static void main(String[] args) {
        String s1 = "ab";
        String s2 = "eidbaooo";
        System.out.println(checkInclusion(s1, s2));
    }

    //滑动窗口+双指针
    public static boolean checkInclusion(String s1, String s2) {
        //首先记录长度
        int n = s1.length(), m = s2.length();
        if (n > m) {
            return false;
        }
        int[] aS1 = new int[26];
        int[] aS2 = new int[26];
        //首先统计这两个字符串以s1长度的每个元素出现的次数
        for (int i = 0; i < n; i++) {
            aS1[s1.charAt(i) - 'a']++;
            aS2[s2.charAt(i) - 'a']++;
        }
        //接下来采用滑动窗口，定义两个指针
        int left = 0, right = n - 1;
        while (right < m) {
            //如果前三个就是一样的直接返回了
            if (Arrays.equals(aS1, aS2)) {
                return true;
            }
            //右指针往前走
            right++;
            if (right != m) {
                //非常天才的地方
                aS2[s2.charAt(right) - 'a']++;
            }
            aS2[s2.charAt(left) - 'a']--;
            left++;

        }
        return false;
    }

}
